1. Field of the Invention
The present invention relates to the processing of digital signals to render Huffman coding with minimal of hardware.
2. Description of Related Art
The digital-signal processing technique of Huffman coding is one of the most pervasive compression means in use today. It has earned a principle position as an enabling component in more sophisticated and specialized compression standards, such as CCITT (facsimile), JPEG (image) and MPEG (video) coding. The art bears this popularity out. Unparalleled speed and simplicity are at the core of its appeal. Yet, known implementations are neither adequately fast nor sufficiently uncomplicated to match the performance demands exacted by modern applications. Most of the art focuses on either reducing memory consumption or raising performance, but few attempt both simultaneous.
A Huffman decoder receives as input a variable-length encoded codeword and generates as output a fixed-length decoded symbol. If the Huffman codetable--the mapping between input codewords and output symbols--is stored directly, the resultant decoder would be fast, but exorbitantly large. This is never done in practice.
The mapping can be decomposed into smaller codetables, where data is processed over each simultaneously with only one responding with a decoding. This approach is fast for large codewords, but the resultant circuits are needlessly complex and consumptive of space.
It is known that the codetable can be stored as a set of pointers implementing a binary tree, with branches associated with codeword bits and leaves associated with symbols. This arrangement is reasonably compact, but requires a unit increment operation. A modification of this arrangement requires less memory at the expense of a variable increment operation. Due to the nature of tree-based storage, such decoders are serial devices, receiving one bit of the codeword per cycle and producing one symbol after all bits of the codeword have been admitted.
Many decoding styles have the potential to process one symbol every cycle. Nevertheless, representatives of this class of coder, such as the mapping decomposition methods mentioned above, have much slower cycle periods than serial-decoder cycle periods as a result of their complexity. Therefore, though for large codewords the effective throughput engendered by releasing a symbol in one cycle is great, for small codewords the effective throughput is obviously worse. Since Huffman coding compresses by assigning small codewords to the most frequently occurring symbols, the ostensibly dramatic throughput of such devices does not, on average, occur. Serial decoders thus prove faster than these in many circumstances.